package shu;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class binarySearchTree<T extends Comparable<T>>{
//定义节点的结构
    class Node{
        T  val;
         Node right;
         Node left;

         public Node(T val){
             this.val=val;
             this.left=this.right=null;
         }
    }
    //定义根节点
    private Node root;
    //记录树中节点个数
    private int size;
    public binarySearchTree(){
        this.root=null;
        this.size=0;
    }
//判断树是否为空
    public boolean isEmpty(){
        return this.size==0;
    }

//向树中添加节点
    public void add(T ele){
        if (this.root==null){
      Node node=new Node(ele);
      this.size+=1;
      root=node;
        }
        //使用递归的方式添加节点
        else {
            add(root,ele);
        }
    }

    private Node add(Node root, T ele) {
        if (root == null) {
            Node node=new Node(ele);
            return node;
        }
      else  if(ele.compareTo(root.val)>0){
            root.right=add(root.right,ele);
        }
        else {
            root.left=add(root.left,ele);
        }
        return root;
    }

//从树中查找节点
    public Node contains(T ele){
        if(root==null){
            return null;
        }
        return contains(root,ele);
    }

    private Node contains(Node root, T ele) {
        if (root==null){
            return null;
        }
       T val=root.val;
        if(ele.compareTo(val)==0){
            return root;
        }
        else if(ele.compareTo(val)>0){
            return contains(root.right,ele);
        }
        else {
            return contains(root.left,ele);
        }
    }

    public List<T> layerOrder(){
        List<T> list=new ArrayList<>();//建立一个返回的链表
        if(root!=null){//做判断，根节点不为空可继续下去
            Queue<Node> queue=new LinkedList<>();//创建一个队列
            queue.add(root);//将根节点加入队列
            while (!queue.isEmpty()){//当队列不为空
                Node node= queue.poll();//从队列中取出队首元素并保存
                list.add(node.val);//加入返回链表中
                if(node.left!=null){//左树不为空
                  queue.offer(node.left);//将左子树加入队列中
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
       return list;
    }



}
